数据结构(一)单链表、栈、和队列

看到实验室这么多考研的童鞋，自己觉得得去分享点东西把，把自己会的分享给他们吧。

这次只是单链表的创建、插入、删除、查找

单链表的c语言代码加详细注释，双向链表和循环链表待更新

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>//申请和释放内存用

//前提说明 所有的i++ 用 ++i使用，i++需要额外的寄存器 ++i则反，提高运行效率
//如有内存泄漏及溢出或者野指针情况 请及时提出

//带头节点的单链表
typedef struct _linked_list
{
    int data;//这里只是用了一个int当作测试数据，自己可以改
    struct _linked_list *next;//尾指针

}linkedList;//重新命名


void traversing(linkedList *List)//遍历链表
{
    linkedList *p=List->next;//遍历指针p先指向list的第一个位置 而不是头节点位置
    while(p!=NULL)
    {
        printf("%d  ",p->data);

        p=p->next;//不断往下指
    }
    printf("\n");//最后换行
}

void create_tail(linkedList *List,const int n)//尾插法 n表示要插入的个数
{
    linkedList *tail=List;
    tail->next=NULL;//先将尾巴放在链表头的位置，然后才进行尾插
    int temp;//输入值的中间变量
    for(int i=0;i<n;++i)
    {
        printf("请输入第%d节点的数值\n",i+1);

        scanf("%d",&temp);//输入数值
        linkedList *newNode=(linkedList*)malloc(sizeof(linkedList));//申请一个新的节点
        newNode->data=temp;//数值拷贝
        tail->next=newNode;//尾巴的下一个指向新节点
        newNode->next=NULL;//新节点后面没有节点了
        tail=newNode;//新节点变成尾巴
    }

}
int insert_node(linkedList *list,int pos,int data)//pos即插入位置 data即数值
{
    //原理基本上和创建的相似
    //因为c语言没有bool类型 只能用int类型的返回值
    //链表的下标是从1开始的，头节点(没有数值)算0下标，自己也可以修改

    if(pos< 1|| list==NULL) return -1;//插入位置小于1 或者 链表为空 直接失败
    linkedList *head=list;//先指向头节点
    int i=0;//计数 找到插入位置的前驱

    while(head!=NULL)
    {
        if(i==pos-1) break;//找到前驱结点就停止
        ++i;
        head=head->next;
    }
    if(i<pos-1) return -1;//pos长度超过链表长度 插入失败

    linkedList *newNode=(linkedList*)malloc(sizeof(linkedList));//新的节点

    newNode->data=data;
    newNode->next=NULL;
    linkedList *temp;//中间无意义节点

    temp=head->next;
    head->next=newNode;
    newNode->next=temp;
    return 1;//插入成功
}
int select_list(linkedList *list,int x)//查找数值 返回下标数组 不仅仅查找一个数值
{
   int i=1;
   linkedList *p=list->next;//遍历指针指向第一个,同上
   //计数 j为arr的长度
   while(p!=NULL)
   {
       if(p->data==x) return i;//找到返回下标
       ++i;
       p=p->next;
   }
   //找不到返回-1
   return -1;
   //拓展：查找的值不可能是唯一的，可以返回下标数组
}

int delete_list(linkedList *list,int pos)
{
    linkedList *p=list;
    if(pos<1||list==NULL) return -1;//删除失败

    int i=0;
    while(p!=NULL)
    {
        if(i==pos-1) break;//找到前驱结点
        ++i;
        p=p->next;
    }
    if(i<pos-1) return -1;//查找失败，越界
    linkedList *temp=p->next;
    p->next=p->next->next;
    free(temp);
    return 1;
}

int main()
{
    const int n=5;
    linkedList *mylist;
    mylist=(linkedList*)malloc(sizeof(linkedList));//先新建一个头节点
    mylist->next=NULL;

    //大部分的函数我传参都是传的链表的地址
    create_tail(mylist,n);//新建
    traversing(mylist);//遍历

    //插入操作 位置3 数值666 自己也可以输入
    int flag=insert_node(mylist,3,666);
    if(flag!=-1) puts("插入成功,链表如下");
    else puts("插入失败,链表如下");

    traversing(mylist);

    //查找666的位置 肯定是3 因为上边刚插入的
    //查找能做到了 修改也是easy的
    printf("查找的位置%d\n",select_list(mylist,666));

    flag=delete_list(mylist,4);//删掉第4个
    
    if(flag!=-1) puts("删除成功,链表如下");
    else puts("删除失败,链表如下");
    traversing(mylist);
    
    //拓展：将遍历链表改为求链表的长度，自己把头插法补充上吧
    
    return 0;
}

栈： 了解了基本性质就行了，c语言版的没必要，附上c++版的栈类，及常用方法

#include <cstdio>
#include <stack>
using namespace std;

//stack 为模板类 <> 里面用来放数据类型
stack<char> mystack;

int main()
{
   //empty 函数使用  返回bool值 空为true
   if(mystack.empty()) puts("栈是空的");

   //push 入栈    pop 出栈  top  返回栈顶数值<>里面的类型

   mystack.push('h');//1
   mystack.push('e');//2
   mystack.push('l');//3
   mystack.push('l');//4
   mystack.push('o');//5

   while(!mystack.empty())
   {
       char temp=mystack.top();
       mystack.pop();
       printf("%c  ",temp);
   }//打印 o l l e h

   //size 即栈的大小 此时以及pop完毕 栈为空size为0
   printf("\n栈的大小为%d\n",mystack.size());
   

   return 0;
}

福利：附上一个常用好玩东西 啥都能放的数组vector

#include <cstdio>
#include <vector>
#include <algorithm>//算法头文件
using namespace std;

//切记一定有 命名空间std
//vector 为模板类 <> 里面用来放数据类型

typedef pair<int,int> Point;
/*
对组 pair <type,type> 能放下一对数据，常用来表示坐标啊，对应关系啊
pair.fist 顾名思义 第一个数据嘛 pair.second 表示第二个数据

pair<int,int> 我把它定义成新的数据类型 坐标
*/

vector<Point> point_arr;
/*
先说一下构造函数 vector(int)  表示一个长为n数值全为0的数组
啥也没有的话默认为空数组  size() 可以检测出来
*/
bool cmp(const Point a,const Point b);//这个先不用管，下文继续说

int main()
{
    //push_back  什么back？ 那有没有front？
    //对不起 没有 在一个线性数组里面往前插入一个数的时间复杂度是O(n)
    //插一个O（n） 插n个就是O（n^2） 效率可想而知
    point_arr.push_back(Point(1,1));
    point_arr.push_back(Point(1,-3));
    point_arr.push_back(Point(2,4));
    point_arr.push_back(Point(-12,8));
    point_arr.push_back(Point(7,6));//在数组里面放入5个点


    //我想按照y的大小从小到大 把这些点拍个序怎么排
    //冒泡？太慢了  归并排序？自己又写不出来
    //这时候 c++的好用之处就来了,看下一行代码 和最后一个函数

    sort(point_arr.begin(),point_arr.end(),cmp);
    //begin 就相当于首指针  end 就相当于尾指针 两个相减就是数组大小
    //不信的话可以试试，只不过stl把指针简化了，变安全了，改叫迭代器了
    //cmp 就是上文的注释函数 即为排序函数，这个函数可以自己写，想怎么排就怎么排
    //就是调用了系统的 快速排序函数 sort（）


    //排序完了 就得打印了，是不是得pop啊
    //这里可以不用pop 万一这些数据还用呢，pop了就没了
    //这里可以用运算符重载 []  直接用到下标，注意是否越界

    puts("y从小到大的结果:");
    for(unsigned int i=0;i<point_arr.size();++i)
        printf("(%d,%d)\n",point_arr[i].first,//x
               point_arr[i].second//y
               );
    //上面是用[] 可不可以用指针呢？可以，不过叫做迭代器
    //  iterator  这个类型的都叫迭代器

    puts("遍历2:");
    vector<Point>::iterator  itor;//创建一个迭代器对象

    for(itor=point_arr.begin();itor!=point_arr.end();itor++)
    {
        //注意指针的自增运算符 ++  就是移动指针一个位置
        printf("(%d,%d)\n",itor->first,//x
               itor->second//y
               );
    }
    
    //自己写一个按照x排序的吧
    return 0;
}

bool cmp(const Point a,const Point b)
{
    //按照y的大小排序 所以只看second 就行了
    //a b 是有顺序的 第一个参数永远在第二个前面
    if(a.second<b.second)
        return true;//后面比前面小就是true  从小到大 简单易懂
    return false;
}